package cn.edu.xjtu.data_structure.chapter02_stack_queue.queue;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/17 21:29
 */

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * 、
 * 当数据序列是整数类型的数据的时候，数据序列中每个数据的位数不要求等宽，比如：41、21、12、322、44、123、2312、765、56
 * 请使用 radixSort1.txt 文件中的数据进行测试
 * 数据序列是字符串类型的数据的时候，数据序列中每个字符串都是等宽的，比如：
 * "abc","bde","fad","abd","bef","fdd","abe"
 * 请使用 radixSort2.txt 文件中的数据进行测试
 * 当数据序列是字符串类型的数据的时候，如果数据序列中每个字符串不等宽，还能否使 用基数排序思想进行排序？
 * 如果可以，请给出具体的排序思路和实现。
 * 请使用 radixSort3.txt 文件中的数据进行测试
 */
public class RadixSort {
    //数字基数排序
    public static void LSDNumber(int[] numbers) {
        //对数字采用最低位优先法排序
        MyQueue queue = new MyQueue(10, numbers.length);
        int digits = getNumDigits(numbers);
        int mode = 1;
        while (digits != 0) {
            for (int i = 0; i < numbers.length; i++) {
                queue.enqueue((numbers[i] / mode) % 10, numbers[i]);
                //按桶分配,(numbers[i]/mode)%10表示取的位数
            }
            int k = 0;
            for (int j = 0; j < 10; j++) {
                while (!queue.isEmpty(j)) {
                    numbers[k] = (int) queue.dequeue(j);
                    k++;
                }
            }//出队
            digits--;//位上移
            mode = mode * 10;
        }
    }

    //等长字符串基数排序
    public static void LSDString(String[] str) {
        //对字符串采取最低位优先法
        MyQueue queue = new MyQueue(52, str.length);
        //52个桶，区分大小写
        int digits = str[0].length();//等长字符的长度
        while (digits != 0) {
            for (int i = 0; i < str.length; i++) {
                int index = 0;//桶的下标
                if (str[i].charAt(digits - 1) >= 'A' && str[i].charAt(digits - 1) <= 'Z') {
                    index = str[i].charAt(digits - 1) - 'A';
                } else if (str[i].charAt(digits - 1) >= 'a' && str[i].charAt(digits - 1) <= 'z') {
                    index = (str[i].charAt(digits - 1) - 'a') + 26;
                } //区分大小写
                queue.enqueue(index, str[i]);
                //按桶分配
            }
            int k = 0;
            for (int j = 0; j < 52; j++) {
                while (!queue.isEmpty(j)) {
                    str[k] = (String) queue.dequeue(j);
                    k++;
                }
            }//出队
            digits--;//位上移
        }
    }

    //非等长字符串基数排序
    public static void LSDStringNot(String[] str) {
        //对字符串采取最低位优先法
        MyQueue queue = new MyQueue(53, str.length);
        //53个桶，其中第1个桶用来存储字母位数不够的字符，区分大小写
        int digits = getStringDigits(str);//等长字符的最大长度
        for (int i = 0; i < str.length; i++) {
            for (int j = str[i].length(); j < digits; j++) {
                str[i] += "0";
            }
        }//补齐位数
        while (digits!=0) {
            for (int i = 0; i < str.length; i++) {
                int index = 0;//桶的下标
                if (str[i].charAt(digits-1) >= 'A' && str[i].charAt(digits-1) <= 'Z') {
                    index = str[i].charAt(digits-1) - 'A' + 1;
                } else if (str[i].charAt(digits-1) >= 'a' && str[i].charAt(digits-1) <= 'z') {
                    index = str[i].charAt(digits-1) - 'a' + 1 + 26;
                }//区分大小写

                queue.enqueue(index, str[i]);
                //按桶分配
            }
            int k = 0;
            for (int q = 0; q < 53; q++) {
                while (!queue.isEmpty(q)) {
                    str[k] = (String) queue.dequeue(q);
                    k++;
                }
            }//出队
            digits--;//位上移
        }
    }

    //将数字基数排序的结果写入文件
    public static void writeNumber(String fileName) throws IOException {
        List test = new ArrayList<Integer>();

        StreamTokenizer stk = new StreamTokenizer(new FileReader("src/radixSort1.txt"));
        int nextToken = stk.nextToken();
        while (nextToken != StreamTokenizer.TT_EOF) {
            if (nextToken == StreamTokenizer.TT_NUMBER) {
                test.add((int) stk.nval);
            }
            nextToken = stk.nextToken();
        }
        int[] strings = new int[test.size()];
        for (int i = 0; i < strings.length; i++) {
            strings[i] = (int) test.get(i);
        }
        LSDNumber(strings);
        BufferedWriter writer1 = new BufferedWriter(new FileWriter(new File(fileName)));
        for (int i = 0; i < strings.length; i++) {
            writer1.write(strings[i] + " ");
            if ((i + 1) % 100 == 0) writer1.newLine();
        }
        writer1.close();
    }

    //将等长字符串基数排序的结果写入文件
    public static void writeStringSameLength(String fileName) throws IOException {
        List test = new ArrayList<String>();

        StreamTokenizer stk = new StreamTokenizer(new FileReader("src/radixSort2.txt"));
        int nextToken = stk.nextToken();
        while (nextToken != StreamTokenizer.TT_EOF) {
            if (nextToken == StreamTokenizer.TT_WORD) {
                test.add(stk.sval);
            }
            nextToken = stk.nextToken();
        }
        System.out.println(test.size());
        String[] strings = new String[test.size()];
        for (int i = 0; i < strings.length; i++) {
            strings[i] = (String) test.get(i);
        }
        LSDString(strings);
        BufferedWriter writer2 = new BufferedWriter(new FileWriter(new File(fileName)));
        for (int i = 0; i < strings.length; i++) {
            writer2.write(strings[i] + " ");
            if ((i + 1) % 50 == 0) writer2.newLine();
        }
        writer2.close();
    }

    //将非等长基数排序的结果写入文件
    public static void writeStringNotSameLength(String fileName) throws IOException {
        List test = new ArrayList<String>();

        StreamTokenizer stk = new StreamTokenizer(new FileReader("src/radixSort3.txt"));
        int nextToken = stk.nextToken();
        while (nextToken != StreamTokenizer.TT_EOF) {
            if (nextToken == StreamTokenizer.TT_WORD) {
                test.add(stk.sval);
            }
            nextToken = stk.nextToken();
        }
        System.out.println(test.size());
        String[] strings = new String[test.size()];
        for (int i = 0; i < strings.length; i++) {
            strings[i] = (String) test.get(i);
        }
        LSDStringNot(strings);
        BufferedWriter writer2 = new BufferedWriter(new FileWriter(new File(fileName)));
        for (int i = 0; i < strings.length; i++) {
            String string = "";
            for (int j = 0; j < strings[i].length(); j++) {
                if (strings[i].charAt(j) == '0') break;
                string += strings[i].charAt(j);
            }//去掉尾部的0
            writer2.write(string + " ");
            if ((i + 1) % 50 == 0) writer2.newLine();
        }
        writer2.close();
    }

    //获得数字最大位数
    static int getNumDigits(int[] nums) {//获得最大的数的位数
        int max = nums[0];//最大的数
        int digits = 0;//位数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
        }
        while (max / 10 != 0) {
            digits++;
            max = max / 10;
        }
        if (max % 10 != 0) {
            digits++;
        }
        return digits;
    }

    //获得字符串最大长度
    static int getStringDigits(String[] strings) {
        int digits = 0;
        for (int i = 0; i < strings.length; i++) {
            if (strings[i].length() > digits)
                digits = strings[i].length();
        }
        return digits;
    }

    public static void main(String[] args) throws IOException {
        writeNumber("src/sortResult1.txt");
        writeStringSameLength("src/sortResult2.txt");
        writeStringNotSameLength("src/sortResult3.txt");


    }
}








